package bitCalculation;

public class ReorderedPowerOf2869 {

    public boolean reorderedPowerOf2(int n) {
        char[] chars = String.valueOf(n).toCharArray();
        return backtracing(chars,0);
    }

    private boolean backtracing(char[] chars, int index) {
        if (index > chars.length) {
            return false;
        }
        for (int i = index; i < chars.length; i++) {
            swap(chars, i, index);
            if (chars[0] != '0' && powerOf2(Integer.valueOf(String.valueOf(chars)))) {
                return true;
            }
            if(backtracing(chars, index + 1)){
                return true;
            }
            swap(chars, i, index);
        }

        return false;

    }

    private void swap(char[] chars, int first, int second) {
        char temp = chars[first];
        chars[first] = chars[second];
        chars[second] = temp;
    }


    boolean powerOf2(int n) {
        return ((n - 1) & n) == 0;
    }
}
